package com.fengye.algorithms.leecode;

import com.fengye.algorithms.leecode.common.TreeNode;

/**
 * @Author fengye
 * @Date 2023/5/2 11:38
 **/
public class LowestCommonAncestorOfABinaryTree236 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) {
            return root;
        }
        // 找左数
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 找右树
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 左数没有，在右树
        if(left == null) {
            return right;
        }
        // 右数没有，在左树
        if(right == null) {
            return left;
        }

        // 如果左数和右树都不为空，说明一个在左一个在右
        return root;
    }
}
